package mo.tags.stack;

import mo.common.ListNode;

import java.util.ArrayList;
import java.util.List;

public class LO2_26 {

    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> nodes = new ArrayList<>();
        ListNode tmp = head;
        while (tmp != null) {
            nodes.add(tmp);
            tmp = tmp.next;
        }
        if (nodes.size() <= 2) {
            return;
        }

        int times = (nodes.size() - 1) / 2;
        ListNode cur = head;
        while (times > 0) {
            ListNode tail = nodes.remove(nodes.size()-1);
            ListNode tailHead = nodes.get(nodes.size()-1);
            tailHead.next = null;
            ListNode next = cur.next;
            cur.next = tail;
            tail.next = next;
            cur = next;
            times--;
        }
    }

}
